#include <cstdio>
int lower_bound(int a[], int left, int right, int t)
{
    int mid;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (a[mid] >= t)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return right;
}
int upper_bound(int a[], int left, int right, int t)
{
    int mid;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (a[mid] > t)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return right;
}
int main()
{
    int a[] = {1, 2, 3, 3, 3, 3, 6, 7};
    int lower = lower_bound(a, 0, sizeof(a) / sizeof(int) - 1, 3);
    int upper = upper_bound(a, 0, sizeof(a) / sizeof(int) - 1, 3);
    printf("interval=[%d,%d)\n", lower, upper);
}